package com.example.demo.arithmetic.datastructure;


import java.util.Collections;
import java.util.List;

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (nums[m] < target) {
                i = m + 1;
            } else if (nums[m] > target) {
                j = m - 1;
            } else {
                return m;
            }
        }
        return i;
    }

    public static void main(String[] args) {
//        System.out.println(new Solution().searchInsert(new int[]{1, 3, 5, 6}, 7));
//        System.out.println(new Solution2().getMax(new int[]{6, 5, 7, 4, 3, 2, 3, 2}));
        System.out.println(new Solution3().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
    }

//    class Solution2 {
//        public int findPeakElement(int[] nums) {
//            int k = 0;
//            for (int i = 0; i < nums.length; i++) {
//                if (i == 0 && nums[i] > nums[i + 1]) {
//                    k = i;
//                } else if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
//                    k = i;
//                } else if (i == nums.length - 1 && nums[i] > nums[i - 1]) {
//                    k = i;
//                }
//            }
//            return k;
//        }
//    }

    static class Solution2 {

        public int getMax(int[] nums) {
            int max = 0;
            if (nums.length == 1) {
                return nums[0];
            }
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > nums[max]) {
                    max = i;
                }
            }

            return max;
        }
    }

    static class Solution3 {
        //输入：nums = [4,5,6,7,0,1,2], target = 0
        //输出：4
        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[left] <= nums[mid]) {
                    if (target >= nums[left] && target < nums[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else if (nums[mid] <= nums[right]) {
                    if (target <= nums[right] && target > nums[mid]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }
    }
}